#include <iostream>
#include <queue>
#include <string>
#include <vector>

struct person {
    std::string name;
    int age;
    person(std::string n, int a) : name(n), age(a) {};
    // 可选：定义输出流运算符，方便打印
    friend std::ostream &operator<<(std::ostream &os, const person &p)
    {
        os << "name: " << p.name << ", age: " << p.age;
        return os;
    }
};

struct person_minheap {
    bool operator()(person &p1, person &p2) { return p1.age > p2.age; }
};

struct person_maxheap {
    bool operator()(person &p1, person &p2) { return p1.age < p2.age; }
};

void traversal_pri_queue(std::priority_queue<int, std::vector<int>, std::greater<int>> queue)
{
    std::cout << "遍历优先队列: \n";
    while (!queue.empty()) {
        std::cout << queue.top() << " ";
        queue.pop();
    }
    std::cout << std::endl;
}

void traversal_pri_queue(std::priority_queue<int> queue)
{
    std::cout << "遍历优先队列: \n";
    while (!queue.empty()) {
        std::cout << queue.top() << " ";
        queue.pop();
    }
    std::cout << std::endl;
}

void traversal_pri_queue(std::priority_queue<person, std::vector<person>, person_minheap> queue)
{
    std::cout << "遍历优先队列: \n";
    while (!queue.empty()) {
        std::cout << queue.top() << " ";
        queue.pop();
    }
    std::cout << std::endl;
}

void traversal_pri_queue(std::priority_queue<person, std::vector<person>, person_maxheap> queue)
{
    std::cout << "遍历优先队列: \n";
    while (!queue.empty()) {
        std::cout << queue.top() << " ";
        queue.pop();
    }
    std::cout << std::endl;
}

int main()
{
    std::vector<int> create_vec = {90, 100, 170, 321, 11, 231, 9, 50, 22};
    /* 1. 等价于 std::priority_queue<int, std::vector<int>, std::less<int>> max_heap; */
    /* 2. 使用vector直接初始化堆 */
    std::priority_queue<int> max_heap(create_vec.cbegin(), create_vec.cend());
    std::priority_queue<int, std::vector<int>, std::greater<int>> min_heap;

    /* 3. 逐个插入元素，建立堆 */
    for (int const &num : create_vec) {
        min_heap.push(num);
    }
    /* 测试标准方法定义的大顶堆和小顶堆 */
    std::cout << "大顶堆的遍历顺序：\n";
    traversal_pri_queue(max_heap);
    std::cout << std::endl;

    std::cout << "小顶堆的遍历顺序：\n";
    traversal_pri_queue(min_heap);

    /* 测试自定义比较函数 */
    std::vector<person> person_info = {person("Alice", 25), person("Bob", 20), person("Jack", 10)};
    std::priority_queue<person, std::vector<person>, person_maxheap> person_maxheap(person_info.cbegin(), person_info.cend());
    std::priority_queue<person, std::vector<person>, person_minheap> person_minheap(person_info.cbegin(), person_info.cend());

    std::cout << "person大顶堆的遍历顺序：\n";
    traversal_pri_queue(person_maxheap);
    std::cout << std::endl;

    std::cout << "person小顶堆的遍历顺序：\n";
    traversal_pri_queue(person_minheap);

    return 0;
}